package com.example.algorithm.greedy;

import sun.awt.geom.AreaOp;

/**
 * @author : zhy
 * @since : 2022/8/30
 * 加油站
 */
public class GasStation {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum=0;
        int min=0;
        int len=gas.length;
        for(int i=0;i<len;i++)
        {
            sum+=(gas[i]-cost[i]);
            min=Math.min(sum,min);
        }
        //总油量不够行驶
        if(sum<0){
            return -1;
        }
        //表示一开始油量就足够
        if(min>=0) {
            return 0;
        }
        //从后往前遍历，找到可以填补这个min的区间
        for(int i=len-1;i>0;i--)
        {
            min+=(gas[i]-cost[i]);
            if(min>=0){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        GasStation gasStation = new GasStation();
        int []gas={1,2,3,4,5};
        int []cost={3,4,5,1,2};
        System.out.println(gasStation.canCompleteCircuit(gas, cost));
    }
}
